#include <bits/stdc++.h>
// 2025/03/02
// tag: 
// Author: Forever
using namespace std;

#pragma GCC optimize("Ofast")

using int64 = int64_t;

int cnt, n, p, ansl[500001], ansr[500001];
stack<int> st[3];

void move(int x, int y){
    if (st[y - 1].empty() || st[x - 1].top() != st[y - 1].top())
        st[y - 1].push(st[x - 1].top());
    st[x - 1].pop();
    ansl[++cnt] = x, ansr[cnt] = y;
}

void solve(){
    cin >> n >> p;
    st[0] = stack<int>(), st[1] = stack<int>(), st[2] = stack<int>();
    cnt = 0;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (st[0].empty() || s[i] - '0' != st[0].top())
            st[0].push(s[i] - '0');
    }
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (st[1].empty() || s[i] - '0' != st[1].top())
            st[1].push(s[i] - '0');
    }
    while (true){
        if (st[0].size() == 1 && st[1].size() == 1 && st[0].top() != st[1].top()){
            if (st[2].empty())
                break;
            if (st[0].top() == st[2].top())
                move(3, 1);
            else
                move(3, 2);
            break;
        }
        else if (st[0].empty()){
            if (st[1].size() == 1){
                move(3, 1);
                break;
            }
            move(2, 1);
        } else if (st[1].empty()) {
            if (st[0].size() == 1) {
                move(3, 2);
                break;
            }
            move(1, 2);
        }
        else if (st[0].size() && st[1].size() &&  st[0].top() == st[1].top()){
            if (st[0].size() > st[1].size())
                move(1, 2);
            else
                move(2, 1);
        }
        else if (st[2].empty()){
            if (st[0].size() > st[1].size())
                move(1, 3);
            else
                move(2, 3);
        }
        else if (!st[0].empty() && st[0].top() == st[2].top())
            move(1, 3);
        else if (!st[1].empty() && st[1].top() == st[2].top())
            move(2, 3);
    }
    cout << cnt << endl;
    if (p > 1)
        for (int i = 1; i <= cnt; i++)
            cout << ansl[i] << " " << ansr[i] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}